<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /* 
            目标和 II：
            输入：nums = [1,1,1,1,1], target = 3
            输出：5
            解释：一共有 5 种方法让最终目标和为 3 。
            -1 + 1 + 1 + 1 + 1 = 3
            +1 - 1 + 1 + 1 + 1 = 3
            +1 + 1 - 1 + 1 + 1 = 3
            +1 + 1 + 1 - 1 + 1 = 3
            +1 + 1 + 1 + 1 - 1 = 3

            采用一维dp的解法：
            1. 初始化长度为n+1数组；第0个和第nums[0]个初始化为1或2
            2. 若nums[i] > j，背包放不下，dp[j] = dp[j] 不变
               否则，为dp[j] +=


        */
        var findTargetSumWays = function(nums, target) {
            let sum = 0   // 总和
            nums.forEach(num => sum += num)
            // 若sum+target不是非零偶数，表示无法找到对应的left值(+的序列组合)，无方案
            if ((sum + target) % 2 !== 0) return 0
            // target的绝对值大于sum, 无方案
            if (Math.abs(target) > sum) return 0
            let left = (sum + target)  / 2
            // 初始化数组
            // let dp = Array.from({length: nums.length + 1}, (item, index) => new Array(left + 1).fill(0))
            let n = nums.length
            // 一维是n nums的长度，因为从0到n-1都会用到，n - 1也是一个物品，不需要n
            // 二维是 left+1，需要取到left的重量
            let dp = new Array(left + 1).fill(0)
            // 第一个物品如果比left小，初始化第一个物品对应的列
            if (nums[0] <= left) dp[nums[0]] = 1
            // 第[0][0]个如果是0，+或者-都可以，第一个应该初始为2,否则为1
            if (nums[0] === 0) dp[0] = 2
            else dp[0] = 1
            // i要比n小，取到n-1个物品，
            for (let i = 1; i < n; i++) {
                // j要取到left，重量需要为left
                for (let j = left; j >= nums[i]; j--) {
                    // 这里不是取最大值，而是求和
                    dp[j] = dp[j] + dp[j - nums[i]]
                }
            }
            return dp[left]
        };
        // console.log(findTargetSumWays([1,1,1,1,1], 3));
        // console.log(findTargetSumWays([1], 1));
        console.log(findTargetSumWays([0,0,0,0,0,0,0,0,1], 1));
    </script>
</body>

</html>